状压DP 奶牛混合起来Mixed Up Cows

发表于 | 评论数： | 阅读次数：

状压DP，顾名思义，将DP中的状态压缩，常用二进制表示图的状态

不多BB，直接看题

奶牛混合起来 $Mixed Up Cows$：https://www.luogu.org/problemnew/show/P2915

我们用二进制来表示当前摆放的奶牛

$eg.$ 0101 表示第一，三个位置没有奶牛，二，四放了奶牛

但是我们要判断的是这个队伍是否“混乱”

混乱的定义是：相邻奶牛的编号之差均超过K

于是我们在由一个状态得到一个新状态时一定要去判断这个原状态加上那个我们新添加到队伍末尾的那只奶牛后是否还是混乱的

那么我们要怎么做呢? （快说啊喂

显然我们的DP数组里存的不止是状态了，还应该存一个能帮助我们判断的东西

那就想想我们一旦新在队伍末尾加入一个奶牛后是怎么判断的呢

很显然只要新加入的这只奶牛和原本队尾那只奶牛的编号差大于k就可以使队伍继续混乱下去了，因为我们必须保证那个原来的状态是合法的，也就是说原来的那个队伍是混乱的

于是我们的状态就呼之欲出了

设 $f[i][j]$ 表示以第i只奶牛为结尾的状态为j的队伍混乱的方案数是多少

而我们怎么转移状态呢，我们知道对于每一个状态都有很多结尾，于是我们用两个循环，一个枚举状态，一个枚举结尾的奶牛

当然我们还需要判断这个情况是否存在

最后我们统计答案的时候要把枚举各种奶牛作为结尾且所有奶牛均被选择的情况

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,a[1<<17],f[17][1<<17],ans;
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		f[i][1<<(n-i)]=1;
	for(int i=1;i<(1<<n);i++)
		for(int j=1;j<=n;j++)
		{
			if(f[j][i])continue;
			if(!(i&(1<<(n-j))))continue;
			int res=i^(1<<(n-j));
			for(int p=1;p<=n;p++)
				if(p!=j&&abs(a[j]-a[p])>k)f[j][i]+=f[p][res];
		}
	for(int i=1;i<=n;i++)
		ans+=f[i][(1<<n)-1];
	printf("%lld\n",ans);
}

撒$fafa$~